# 53. 最大子序和
# https://leetcode-cn.com/problems/maximum-subarray/
# 给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
#
#
#
# 示例 1：
#
# 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
# 输出：6
# 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
# 示例 2：
#
# 输入：nums = [1]
# 输出：1
# 示例 3：
#
# 输入：nums = [0]
# 输出：0
# 示例 4：
#
# 输入：nums = [-1]
# 输出：-1
# 示例 5：
#
# 输入：nums = [-100000]
# 输出：-100000
#
#
# 提示：
#
# 1 <= nums.length <= 105
# -104 <= nums[i] <= 104
#
import math
from typing import List


class Solution1:
    def maxSubArray(self, nums: List[int]) -> int:
        """
        暴力求解   超时了
        :param nums:
        :return:
        """
        d = [[0 for _ in range(len(nums) + 1)] for _ in range(len(nums) + 1)]
        max_dist = -math.inf
        for len_ in range(1, len(nums) + 1):
            for i in range(len(nums)):
                if i + len_ > len(nums):
                    break
                d[i][i + len_] = d[i][i + len_ - 1] + nums[i + len_ - 1]
                if max_dist < d[i][i + len_]:
                    max_dist = d[i][i + len_]
        return max_dist


class Solution2:
    def maxSubArray(self, nums: List[int]) -> int:
        """
        暴力求解+预计算
        ----
        1.暴力求解
        max(sum(nums[i:j+1]))
        2.预计算 空间复杂度: O(N^2), 时间复杂度: O(N^2)
        sum(nums[i:(j+1)]) = sum(nums[i:j-1]) + nums[j]
        sum(nums[i:(j+1)]) = nums[i] + sum(nums[i-1:j])
        3.进一步优化, 将决策放到子问题中, 节省空间复杂度
        预计算sum(nums[i:(j+1)])改为i:j+1的最大值d
        d[i][j] = max(d[i][j-1] + nums[j], nums[j], d[i+1][j], nums[i])
        :param nums:
        :return:
        """
        d = [[0 for _ in range(len(nums) + 1)] for _ in range(len(nums) + 1)]
        max_dist = -float('inf')
        for len_ in range(1, len(nums) + 1):
            for i in range(len(nums)):
                if i + len_ > len(nums):
                    break
                j = i + len_
                d[i][j] = max(d[i][j - 1] + nums[j - 1], nums[j - 1])
                if max_dist < d[i][j]:
                    max_dist = d[i][j]
        return max_dist


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        """
        动态规划:
        - d[i]为以nums[i]结尾的序列的最大子序和
        - d[i] = nums[i]
        - d[i+1] = max(nums[i+1], d[i] + nums[i+1])
        :param nums:
        :return:
        """
        if not len(nums):
            return None
        d = [nums[i] for i in range(len(nums))]

        max_dist = nums[0]
        for i in range(1, len(nums)):
            d[i] = max(d[i - 1] + nums[i], nums[i])
            if max_dist < d[i]:
                max_dist = d[i]
        return max_dist


solution = Solution1()
assert solution.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert solution.maxSubArray([-100000]) == -100000
assert solution.maxSubArray([1]) == 1
print(solution.maxSubArray([1]))

# -2, 2, -3, 1, -1, 4, -1, 2, 1, -5, 4
# i
#
#
